Recursion in simple math¶
Template¶
import sys
# Expected output:
# Forward, N=5
# Forward, N=4
# Forward, N=3
# Forward, N=2
# Base case
# Backward, N=2
# Backward, N=3
# Backward, N=4
# Backward, N=5
def template(N):
''' Recursion idea '''
if N == 1:
print("Base case")
else:
print("Forward, N={}".format(N))
template(N-1)
print("Backward, N={}".format(N))
sum(A)¶
def sum_recursion(A):
''' Summ of elements in the list [recursion]. '''
if A == []: # base case - empty list
return 0
return A[0] + sum_recursion(A[1:]) # rescursion
def sum_regular(A):
''' Summ of elements in the list [regular]. '''
res = 0
for val in A:
res += val
return res
length(A)¶
def length_recursion(A):
''' Number of elements in the list [recursion]. '''
if A == []: # base case - empty list
return 0
return 1 + length_recursion(A[1:])
def length_regular(A):
''' Number of elements in the list [regular]. '''
return len(A)
max(A)¶
def max_recursion(A):
''' Max element in the list [recursion]. '''
if len(A) == 2: # base case - only 2 elements in the list
return A[0] if A[0] > A[1] else A[1]
sub_max = max_recursion(A[1:]) # recursion for other elements
return A[0] if A[0] > sub_max else sub_max
def max_regular(A):
''' Max element in the list [regular]. '''
max_num = 0
for i in range(len(A)):
if A[i] >= max_num:
max_num = A[i]
return max_num
min(A)¶
def min_recursion(A):
''' Min element in the list [recursion]. '''
if len(A) == 2: # base case - only 2 elements in the list
return A[0] if A[0] < A[1] else A[1]
sub_min = min_recursion(A[1:]) # recursion for other elements
return A[0] if A[0] < sub_min else sub_min
def min_regular(A):
''' Min element in the list [regular]. '''
min_num = sys.maxsize
for i in range(len(A)):
if A[i] <= min_num:
min_num = A[i]
return min_num
factorial(N)¶
def factorial_recursion(N):
''' Factorial n! = n*(n-1)!] calculation [recursion]. '''
# f(n) = 1, if n = 0
# f(n) * n, if n > 1
assert N >=0, "Factorial is not defined"
if N == 0: # base case
return 1
return factorial_recursion(N - 1) * N
def factorial_regular(N):
''' Factorial n! = n*(n-1)!] calculation [regular]. '''
fact = 1
x = 2
while x <= N:
fact *= x
x += 1
return fact
gcd(N, M)¶
# Great common divisor [GCD] = Euclide algorithm.
# a |---+---+---+---+---+---|
# b |---+---+---|< a - b >|
#
# = a, if a= b
# GCD(a, b) = GCD(a-b, b), if a > b
# = GCD(a, b-a), if b > a
def gcd_recursion(a, b):
''' Great common divisor [GCD]. '''
if a == b: # base case
return a
elif a > b:
return gcd_recursion(a - b, b)
else: # a < b
return gcd_recursion(a, b - a)
# GCD(a, b) = GCD(b, a % b)
#
# = a, if b = 0
# GCD(a, b) = GCD(b, a % b)
#
def gcd_recursion1(a, b):
if b == 0: # base case
return a
else:
return gcd_recursion1(b, a % b)
# OR
# def gcd2(a, b):
# return a if b == 0 else gcd(b, a % b)
pwr(N)¶
# a ^ N = a * a * a * ... * a
# OR
# = 1, if N = 0
# a^N = a^(N-1) * a, where N - integer, N > 0
# But:
# a^N = a^2^(N/2)
# then
# = 1, if N = 0
# a^N = a^(N-1) * a, where N - odd
# = a^2(N//2), where N - even
# O(log2(N))
def quick_power(a : float, N : int):
''' Quick Power. '''
if N == 0:
return 1
elif N % 2 == 1: # odd
return quick_power(a, N -1) * a
else:
return quick_power(a**2, N//2)
Tests:
def test_sum(algorithm):
print("Testing:", algorithm.__doc__)
print("testcase #1: ", end="")
A = [1, 2, 3, 4]
N = 10
Res = algorithm(A)
print("Ok" if Res == N else "Fail")
def test_length(algorithm):
print("Testing:", algorithm.__doc__)
print("testcase #2: ", end="")
A = [1, 2, 4, 34, 55, 21, 23]
N = 7
Res = algorithm(A)
print("Ok" if Res == N else "Fail")
def test_max(algorithm):
print("Testing:", algorithm.__doc__)
print("testcase #3: ", end="")
A = [1, 2, 22, 32, 55, 3, 18]
N = 55
Res = algorithm(A)
print("Ok" if Res == N else "Fail")
def test_min(algorithm):
print("Testing:", algorithm.__doc__)
print("testcase #4: ", end="")
A = [22, 34, 34, 12, 56, 234]
N = 12
Res = algorithm(A)
print("Ok" if Res == N else "Fail")
def test_factorial(algorithm):
print("Testing:", algorithm.__doc__)
print("testcase #5: ", end="")
N = 10
R = 3628800
Res = algorithm(N)
print("Ok" if Res == R else "Fail")
def test_gcd(algorithm):
print("Testing:", algorithm.__doc__)
print("testcase #6: ", end="")
A, B = 36, 60
R = 12
Res = algorithm(A, B)
print("Ok" if Res == R else "Fail")
def test_quick_power(algorithm):
print("Testing:", algorithm.__doc__)
print("testcase #7: ", end="")
A, B = 3, 12
R = 531441 # print(math.pow(3, 12))
Res = algorithm(A, B)
print("Ok" if Res == R else "Fail")
if __name__ == "__main__":
template(5)
test_sum(sum_recursion)
test_sum(sum_regular)
test_length(length_recursion)
test_length(length_regular)
test_max(max_recursion)
test_max(max_regular)
test_min(min_recursion)
test_min(min_regular)
test_factorial(factorial_recursion)
test_factorial(factorial_regular)
test_gcd(gcd_recursion)
test_quick_power(quick_power)